package com.asia.algorithmcode.dynamicProgram;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @DESCRIPTION: 123、买卖股票的最佳时机 3
 * @USER: wanfu
 * @DATE: 2025/6/5 星期四 14:10
 */
public class MaxProfit3 {


    public static void main(String[] args) {
//        int[] arr = {7, 1, 5, 3, 6, 4};
//        int[] arr = {1, 2, 3, 4, 5};
//        int[] arr = {3, 3, 5, 0, 0, 3, 1, 4};
        int[] arr = {1, 2, 4, 2, 5, 7, 2, 4, 9, 0};
//        int[] arr = {1};


        System.out.println(new MaxProfit3().maxProfit(arr));
    }


    /**
     * 动态规划的写法
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        /*
        arr[i][0] 表示不做买入卖出动作
        arr[i][1] 表示第一次买入
        arr[i][2] 表示第一次卖出
        arr[i][3] 表示第二次买入
        arr[i][4] 表示第二次卖出
         */
        int[][] arr = new int[n][5];
        /*
        初始状态，第一天 第一次买入或者第二次买入
         */
        arr[0][1] = -prices[0];
        arr[0][3] = -prices[0];

        for (int i = 1; i < n; i++) {
            arr[i][0] = arr[i - 1][0];
            arr[i][1] = Math.max(arr[i - 1][1], arr[i - 1][0] - prices[i]); // 是昨天买了大，还是昨天没买，今天买了大
            arr[i][2] = Math.max(arr[i - 1][2], arr[i - 1][1] + prices[i]); // 是昨天卖了大，还是昨天买，今天卖大
            arr[i][3] = Math.max(arr[i - 1][3], arr[i - 1][2] - prices[i]); // 是昨天买了大，还是昨天卖了，今天买大
            arr[i][4] = Math.max(arr[i - 1][4], arr[i - 1][3] + prices[i]); // 是昨天卖了大，还是昨天买，今天卖大
        }
        return arr[n - 1][4];
    }


    /**
     * 前缀和分解
     *
     * @param prices
     * @return
     */
//    public int maxProfit(int[] prices) {
//        int n = prices.length;
//        int[] arr = new int[n + 1];
//
//        for (int i = 1, min = Integer.MAX_VALUE; i < n; i++) {
//            arr[i] = Math.max(arr[i - 1], prices[i - 1] - min);
//            min = Math.min(prices[i - 1], min);
//        }
//
//        int res = 0;
//        for (int i = n, max = 0; i > 0; i--) {
//            res = Math.max(res, max - prices[i - 1] + arr[i - 1]);
//            max = Math.max(max, prices[i - 1]);
//        }
//
//        return res;
//    }

}
